package com.s11.heap;

public class MinHeapTest {

	public static void main(String[] args) {
		MinHeap heap = new MinHeap(3);
		System.out.println("----insert 策略一----");
		heap.insert(2);
		heap.insert(7);
		heap.insert(3);
		heap.insert(5);
		System.out.println(heap);

		// 前 3 大的元素
		int k = 3;
		heap = new MinHeap(k);
		System.out.println("----insert 策略二----");
		heap.insert2(2);
		heap.insert2(7);
		heap.insert2(3);
		heap.insert2(5);
		System.out.println(heap.getTop());

		// 求第 k 个大的数(top k)
		System.out.println("----求第 k 个大的数(top k)----");
		int[] input = new int[] { 2, 7, 3, 5 };
		System.out.println(MinHeap.topK(input, k));
		
		System.out.println("----求中位数----");
		// 求中位数：维护大小堆
		// 如果未满，则继续插入。如果已满判断是否 < 小堆得最大值，则插入大顶堆。
		input = new int[] { 2, 7, 3, 5, 1, 8, 9, 6, 10 };
		int minHeapCapLength = input.length / 2;
		int maxHeapCapLength = input.length / 2;
		if (input.length % 2 == 1) {
			maxHeapCapLength++;
		}
		MinHeap minHeap = new MinHeap(minHeapCapLength);
		MaxHeap maxHeap = new MaxHeap(maxHeapCapLength);
		for (int i = 0; i < input.length; i++) {
			if (i < minHeapCapLength) {
				minHeap.insert2(input[i]);
			} else {
				int data = input[i];
				if (input[i] >= minHeap.getTop()) {
					data = minHeap.getTop();
					minHeap.insert2(input[i]);
				}
				maxHeap.insert(data);
			}
		}
		System.out.println(maxHeap.getTop());
	}

}
